<?php
namespace app\service;

use app\service\PachCreateHelper;

class PachCreate
{
	// 走棋方，红方为0，黑方为1
	private $_side = 0;
	// 棋盘数组
	private $_board = [];
	// 棋子数组
	private $_pieces = [];
	// 走法栈
	private $_moveStack = [];
	// 当前搜索深度
	private  $_ply = 0;
	// 最大搜索深度
	private $_maxDepth = 3;
	// 搜索出来的最佳走法
	private $_bestMove = [];
	
	public $times = 0;
	
	public function getMaxDepth() {
		return $this->_maxDepth;
	}

	public function getBestMove() {
		return $this->_bestMove;
	}

	public function setMaxDepth($_maxDepth) {
		$this->_maxDepth = $_maxDepth;
	}

	public function setPieces($_pieces) {
		$this->_pieces = $_pieces;
	}

	public function setSide($side) {
		$this->_side = $side;
	}

	public function setBoard($board) {
		$this->_board = $board;
	}
	
	/**
	 * 保存走法
	 * @param int $from
	 * @param int $to
	 */
	public function saveMove($from, $to, &$moveList)
	{
		// 生成走棋之后的局面
		$eatKey = $this->_board[$to];
		$this->_pieces[$this->_board[$from]] = $to;
		if($eatKey)	// 吃子
		{
			$this->_pieces[$eatKey] = 0;
		}
		$this->_board[$to] = $this->_board[$from];
		$this->_board[$from] = 0;
		
		// 判断是否被将军
		$attack = $this->check($this->_side);
		
		// 恢复棋局
		$this->_board[$from] = $this->_board[$to];
		$this->_board[$to] = $eatKey;
		$this->_pieces[$this->_board[$from]] = $from;
		if($eatKey)	// 吃子
		{
			$this->_pieces[$eatKey] = $to;
		}
		
		if(!$attack)	// 未被将军时，才保存走法
		{
			$moveList[] = [$from, $to];
		}
	}
	
	/**
	 * 生成马的走法
	 * @param int $position 马的位置
	 */
	public function knightMove($position, &$moveList)
	{
		$nextPosition = 0;	// 下一步可能走的位置
		$checkPosotion = 0;	// 马腿位置
		$sideTag = 16 + $this->_side * 16;	// 走棋方，红方16，黑方32
		
		for($k=0; $k<8; $k++)	// 8个方向
		{
			$nextPosition = $position + PachCreateHelper::$knightDir[$k];
			//if(PachCreateHelper::$knightPosition[$nextPosition])	// 是否在棋盘上
			if(PachCreateHelper::$legalPosition[$this->_side][$nextPosition] & PachCreateHelper::$positionMask[3])
			{
				$checkPosotion = $position + PachCreateHelper::$knightCheck[$k];
				if(!$this->_board[$checkPosotion])	// 马腿位置无棋子
				{
					if(!($this->_board[$nextPosition] & $sideTag))	// 目标位置上没有本方棋子
					{
						$this->saveMove($position, $nextPosition, $moveList);
					}
				}
			}
		}
		
	}
	
	/**
	 * 生成将（帅）的走法
	 * @param int $position 将的位置
	 */
	public function kingMove($position, &$moveList)
	{
		$nextPosition = 0;	// 下一步可能走的位置
		$sideTag = 16 + $this->_side * 16;	// 走棋方，红方16，黑方32
		for($k=0; $k<4; $k++)	// 4个方向
		{
			$nextPosition = $position + PachCreateHelper::$kingDir[$k];
			//if(PachCreateHelper::$kingPosition[$nextPosition])	// 是否在九宫格中
			if(PachCreateHelper::$legalPosition[$this->_side][$nextPosition] & PachCreateHelper::$positionMask[0])
			{
				if(!($this->_board[$nextPosition] & $sideTag))	// 目标位置上没有本方棋子
				{
					$this->saveMove($position, $nextPosition, $moveList);
				}
			}
		}
	}
	
	/**
	 * 生成仕的走法
	 * @param int $position 仕的位置
	 */
	public function AdvisorMove($position, &$moveList)
	{
		$nextPosition = 0;	// 下一步可能走的位置
		$sideTag = 16 + $this->_side * 16;	// 走棋方，红方16，黑方32
		for($k=0; $k<4; $k++)	// 4个方向
		{
			$nextPosition = $position + PachCreateHelper::$advisorDir[$k];
			//if(PachCreateHelper::$advisorPosition[$nextPosition])
			if(PachCreateHelper::$legalPosition[$this->_side][$nextPosition] & PachCreateHelper::$positionMask[1])
			{
				if(!($this->_board[$nextPosition] & $sideTag))	// 目标位置上没有本方棋子
				{
					$this->saveMove($position, $nextPosition, $moveList);
				}
			}
		}
	}
	
	/**
	 * 生成象的走法
	 * @param int $position 象的位置
	 */
	public function BishopMove($position, &$moveList)
	{
		$nextPosition = 0;	// 下一步可能走的位置
		$checkPosotion = 0;	// 象眼位置
		$sideTag = 16 + $this->_side * 16;	// 走棋方，红方16，黑方32
		for($k=0; $k<4; $k++)	// 4个方向
		{
			$nextPosition = $position + PachCreateHelper::$bishopDir[$k];
			//if(PachCreateHelper::$bishopPosition[$nextPosition])
			if(PachCreateHelper::$legalPosition[$this->_side][$nextPosition] & PachCreateHelper::$positionMask[2])
			{
				$checkPosotion = $position + PachCreateHelper::$bishopCheck[$k];
				if(!$this->_board[$checkPosotion])	// 象眼位置无棋子
				{
					if(!($this->_board[$nextPosition] & $sideTag))	// 目标位置上没有本方棋子
					{
						$this->saveMove($position, $nextPosition, $moveList);
					}
				}
			}
		}
	}
	
	/**
	 * 生成车的走法
	 * @param int $pisotion 车的初始位置
	 */
	public function rookMove($position, &$moveList)
	{
		$nextPosition = 0;	// 下一步可能走的位置
		$sideTag = 16 + $this->_side * 16;	// 走棋方，红方16，黑方32
		for($k=0; $k<4; $k++)	// 4个方向
		{
			for($j=1; $j<10; $j++)	// 横向最多8个位置，纵向最多9个
			{
				$nextPosition = $position + $j*PachCreateHelper::$rookDir[$k];
				//if(!PachCreateHelper::$knightPosition[$nextPosition])	// 不合理的位置，其实就是不在棋盘上
				if(!(PachCreateHelper::$legalPosition[$this->_side][$nextPosition] & PachCreateHelper::$positionMask[4]))
				{
					break;
				}
				
				if(!$this->_board[$nextPosition])	// 目标位置无子
				{
					$this->saveMove($position, $nextPosition, $moveList);
				}
				else if($this->_board[$nextPosition] & $sideTag)	// 目标位置有本方棋子
				{
					break;
				}
				else	// 目标位置有对方棋子
				{
					$this->saveMove($position, $nextPosition, $moveList);
					break;
				}
			}
		}
	}
	
	/**
	 * 生成炮的走法
	 * @param int $position 炮的初始位置
	 */
	public function cannonMove($position, &$moveList)
	{
		$nextPosition = 0;	// 下一步可能走的位置
		$sideTag = 16 + $this->_side * 16;	// 走棋方，红方16，黑方32
		$overFlag = 0;	// 是否翻山，已翻0，未翻1
		for($k=0; $k<4; $k++)	// 4个方向
		{
			$overFlag = 0;
			for($j=1; $j<10; $j++)	// 横向最多8个位置，纵向最多9个
			{
				$nextPosition = $position + $j*PachCreateHelper::$cannonDir[$k];
				//if(!PachCreateHelper::$knightPosition[$nextPosition])	// 不合理的位置，其实就是不在棋盘上
				if(!(PachCreateHelper::$legalPosition[$this->_side][$nextPosition] & PachCreateHelper::$positionMask[5]))
				{
					break;
				}
				
				if(!$this->_board[$nextPosition])	// 目标位置无子
				{
					if(!$overFlag)	// 未翻山
					{
						$this->saveMove($position, $nextPosition, $moveList);
					}
					// 已翻山则不作处理，考察下一位置
				}
				else	// 目标位置上有子
				{
					if(!$overFlag)	// 未翻山，则置翻山标志
					{
						$overFlag = 1;
					}
					else
					{
						if(!($this->_board[$nextPosition] & $sideTag))	// 对方棋子
						{
							$this->saveMove($position, $nextPosition, $moveList);
						}
						break;	// 这是在已翻山的情况下，又遇到了棋子。不管这事对方棋子还是己方棋子，都要退出该方向的搜索了。
					}
				}
			}
		}
	}
	
	/**
	 * 生成兵（卒）的走法
	 * @param int $position 兵（卒）的初始位置
	 */
	public function pawnMove($position, &$moveList)
	{
		$nextPosition = 0;	// 下一步可能走的位置
		$sideTag = 16 + $this->_side * 16;	// 走棋方，红方16，黑方32
		for($k=0; $k<3; $k++)	// 3个方向
		{
			$nextPosition = $position + PachCreateHelper::$pawnDir[$this->_side][$k];
			//if(PachCreateHelper::$pawnPosition[$this->_side][$nextPosition])
			if(PachCreateHelper::$legalPosition[$this->_side][$nextPosition] & PachCreateHelper::$positionMask[6])
			{
				if(!($this->_board[$nextPosition] & $sideTag))	// 目标位置上没有本方棋子
				{
					$this->saveMove($position, $nextPosition, $moveList);
				}
			}
		}
	}
	
	/**
	 * 生成一个局面的全部走法
	 */
	public function genAllMove(&$moveList)
	{
		$position = 0;	// 下一步可能走的位置
		$sideTag = 16 + $this->_side * 16;	// 走棋方，红方16，黑方32
		for($i=0; $i<16; $i++)
		{
			$key = $sideTag + $i;
			$position = $this->_pieces[$key];
			if($position == 0)
			{
				continue;
			}
			
			switch($i)
			{
				case 0:	// 帅（将）
					self::kingMove($position, $moveList);
					break;
				case 1:	// 仕
				case 2:
					self::AdvisorMove($position, $moveList);
					break;
				case 3:	// 象
				case 4:
					self::BishopMove($position, $moveList);
					break;
				case 5:	// 马
				case 6:
					self::knightMove($position, $moveList);
					break;
				case 7:	// 车
				case 8:
					self::rookMove($position, $moveList);
					break;
				case 9:
				case 10:
					self::cannonMove($position, $moveList);
					break;
				case 11:
				case 12:
				case 13:
				case 14:
				case 15:
					self::pawnMove($position, $moveList);
					break;
			}
		}
	}
	
	/**
	 * 检测是否被将军
	 * @param int $chkSide 检测$chkSide一方是否被将军
	 */
	public function check($chkSide)
	{
		$attack = 0;	// 是否被将军，1被将军，0未被将军
		$sideTag = 32 - $chkSide * 16;	// 对方棋子，红方32，黑方16
		$oppositeSide = 1 - $chkSide;	// 对方标志
		
		$wKing = $this->_pieces[16];	// 红帅位置
		$bKing = $this->_pieces[32];	// 黑将位置
		if(!$wKing || !$bKing)
		{
			return 0;
		}
		
		// 检测将帅是否照面
		$attack = 1;
		if($wKing%16 == $bKing%16)	// 将帅在同一列
		{
			for($i=$wKing-16; $i!=$bKing; $i=$i-16)
			{
				if($this->_board[$i])
				{
					$attack = 0;
					break;
				}
			}
			
			if($attack)
			{
				return $attack;
			}
		}
		
		$selfKingPosition = $this->_pieces[48 - $sideTag];
		// 检测是否被马将军
		for($i=5; $i<=6; $i++)
		{
			$attackPosition = $this->_pieces[$sideTag + $i];	// 对方的攻击棋子（马）的位置
			if(!$attackPosition)
			{
				continue;
			}
			
			for($k=0; $k<8; $k++)	// 马的8个方向
			{
				$nextPosition = $attackPosition + PachCreateHelper::$knightDir[$k];	// 对方这个马可以走到新位置
				if($nextPosition != $selfKingPosition)
				{
					continue;
				}
				
				if(PachCreateHelper::$legalPosition[$oppositeSide][$nextPosition] & PachCreateHelper::$positionMask[3])
				{
					$knightCheck = $attackPosition + PachCreateHelper::$knightCheck[$k];	// 马腿位置
					if(!$this->_board[$knightCheck])
					{
						return 1;
					}
				}
			}
		}
		
		// 检测是否被车将军
		$attack = 1;
		for($i=7; $i<=8; $i++)
		{
			$attackPosition = $this->_pieces[$sideTag + $i];	// 对方的攻击棋子（车）的位置
			if(!$attackPosition)
			{
				continue;
			}
			
			if($selfKingPosition%16 == $attackPosition%16)	// 在同一列
			{
				$posAdd = ($attackPosition>$selfKingPosition?-16:16);
				for($attackPosition=$attackPosition+$posAdd; $attackPosition!=$selfKingPosition; $attackPosition=$attackPosition+$posAdd)
				{
					if($this->_board[$attackPosition])	// 车将之间隔着棋子
					{
						$attack = 0;
						break;
					}
				}
				
				if($attack)
				{
					return $attack;
				}
			}
			else if(intval($selfKingPosition/16) == intval($attackPosition/16))	// 在同一行
			{
				$posAdd = ($attackPosition>$selfKingPosition?-1:1);
				for($attackPosition=$attackPosition+$posAdd; $attackPosition!=$selfKingPosition; $attackPosition=$attackPosition+$posAdd)
				{
					if($this->_board[$attackPosition])	// 车将之间隔着棋子
					{
						$attack = 0;
						break;
					}
				}
				
				if($attack)
				{
					return $attack;
				}
			}
		}
		
		// 检测是否被炮将军
		for($i=9; $i<=10; $i++)
		{
			$overFlag = 0;	// 翻山标志
			
			$attackPosition = $this->_pieces[$sideTag + $i];	// 对方的攻击棋子（炮）的位置
			if(!$attackPosition)
			{
				continue;
			}
			
			if($selfKingPosition%16 == $attackPosition%16)	// 在同一列
			{
				$posAdd = ($attackPosition>$selfKingPosition?-16:16);
				for($attackPosition=$attackPosition+$posAdd; $attackPosition!=$selfKingPosition; $attackPosition=$attackPosition+$posAdd)
				{
					if($this->_board[$attackPosition])	// 炮将之间隔着棋子
					{
						if(!$overFlag)	// 隔一子
						{
							$overFlag = 1;
						}
						else
						{
							$overFlag = 2;
							break;
						}
					}
				}
				
				if($overFlag == 1)
				{
					return 1;
				}
			}
			else if(intval($selfKingPosition/16) == intval($attackPosition/16))	// 在同一行
			{
				$posAdd = ($attackPosition>$selfKingPosition?-1:1);
				for($attackPosition=$attackPosition+$posAdd; $attackPosition!=$selfKingPosition; $attackPosition=$attackPosition+$posAdd)
				{
					if($this->_board[$attackPosition])	// 炮将之间隔着棋子
					{
						if(!$overFlag)	// 隔一子
						{
							$overFlag = 1;
						}
						else
						{
							$overFlag = 2;
							break;
						}
					}
				}
				
				if($overFlag == 1)
				{
					return 1;
				}
			}
		}
		
		// 检测是否被兵（卒）将军
		for($i=11; $i<=15; $i++)
		{
			$attackPosition = $this->_pieces[$sideTag + $i];	// 对方的攻击棋子（兵）的位置
			if(!$attackPosition)
			{
				continue;
			}
			
			for($k=0; $k<3; $k++)
			{
				$nextPosition = $attackPosition + PachCreateHelper::$pawnDir[$oppositeSide][$k];
				if(($nextPosition==$selfKingPosition) && (PachCreateHelper::$legalPosition[$oppositeSide][$nextPosition]&PachCreateHelper::$positionMask[6]))
				{
					return 1;
				}
			}
			
		}
		
		return 0;
	}
	
	/**
	 * 局面评估
	 */
	public function evaluate()
	{
		$position = 0;	// 棋子位置
		$nextPosition = 0;	// 下一步可能走的位置
		$checkPosition = 0;	// 马腿、象眼的位置
		$sideTag = 16;		// 走棋方，红方16，黑方32
		$overFlag = 0;		// 炮翻山标志
		$wValue = 0;		// 红方分值
		$bValue = 0;		// 黑方分值
		$flexibleValue = [0, 0];	// 灵活性分值
		
		// 计算位置分值
		for($i=16; $i<32; $i++)
		{
			if($this->_pieces[$i] > 0)
			{
				$wValue += PachCreateHelper::$positionValues[0][PachCreateHelper::$pieceNumToType[$i]][$this->_pieces[$i]];	// 位置得分
				//$wValue += PachCreateHelper::$pieceValue[$i];
			}
		}
		
		for($i=32; $i<48; $i++)
		{
			if($this->_pieces[$i] > 0)
			{
				$bValue += PachCreateHelper::$positionValues[1][PachCreateHelper::$pieceNumToType[$i]][$this->_pieces[$i]];
				//$bValue += PachCreateHelper::$pieceValue[$i];
			}
		}
		
		// 计算灵活性分值
		/*for($r=0; $r<=1; $r++)
		{
			$sideTag = 16 + 16*$r;
			
			// 将的灵活性
			$position = $this->_pieces[$sideTag];
			if(!$position)	// 将被吃了
			{
				continue;
			}
			for($k=0; $k<4; $k++)	// 4个方向
			{
				$nextPosition = $position + PachCreateHelper::$kingDir[$k];
				
				if(PachCreateHelper::$legalPosition[$r][$nextPosition] & PachCreateHelper::$positionMask[0])
				{
					if(!($this->_board[$nextPosition] & $sideTag))	// 目标位置没有本方棋子
					{
						$flexibleValue[$r] += 2;
					}
				}
			}

			// 仕的灵活性
			for($i=1; $i<=2; $i++)
			{
				$position = $this->_pieces[$sideTag + $i];
				if(!$position)
				{
					continue;
				}
				for($k=0; $k<4; $k++)	// 4个方向
				{
					$nextPosition = $position + PachCreateHelper::$advisorDir[$k];
					if(PachCreateHelper::$legalPosition[$r][$nextPosition] & PachCreateHelper::$positionMask[1])
					{
						if(!($this->_board[$nextPosition] & $sideTag))	// 目标位置没有本方棋子
						{
							$flexibleValue[$r] += 2;
						}
					}
				}
			}
			
			// 象的灵活性
			for($i=3; $i<=4; $i++)
			{
				$position = $this->_pieces[$sideTag + $i];
				if(!$position)
				{
					continue;
				}
				for($k=0; $k<4; $k++)	// 4个方向
				{
					$nextPosition = $position + PachCreateHelper::$bishopDir[$k];
					if(PachCreateHelper::$legalPosition[$r][$nextPosition] & PachCreateHelper::$positionMask[2])
					{
						$checkPosition = $position + PachCreateHelper::$bishopCheck[$k];	// 象眼位置
						if(!$this->_board[$checkPosition])	// 象眼位置无棋子
						{
							if(!($this->_board[$nextPosition] & $sideTag))	// 目标位置没有本方棋子
							{
								$flexibleValue[$r] += 2;
							}
						}
					}
				}
			}
			
			// 马的灵活性
			for($i=5; $i<=6; $i++)
			{
				$position = $this->_pieces[$sideTag + $i];
				if(!$position)
				{
					continue;
				}
				for($k=0; $k<8; $k++)	// 8个方向
				{
					$nextPosition = $position + PachCreateHelper::$knightDir[$k];
					if(PachCreateHelper::$legalPosition[$r][$nextPosition] & PachCreateHelper::$positionMask[3])
					{
						$checkPosition = $position + PachCreateHelper::$knightCheck[$k];	// 马腿位置
						if(!$this->_board[$checkPosition])	// 马腿位置无棋子
						{
							if(!($this->_board[$nextPosition] & $sideTag))	// 目标位置没有本方棋子
							{
								$flexibleValue[$r] += 5;
							}
						}
					}
				}
			}
			
			// 车的灵活性
			for($i=7; $i<=8; $i++)
			{
				$position = $this->_pieces[$sideTag + $i];
				if(!$position)
				{
					continue;
				}
				for($k=0; $k<4; $k++)	// 4个方向
				{
					for($j=1; $j<10; $j++)	// 横向最多8个位置，纵向最多9个位置
					{
						$nextPosition = $position + $j*PachCreateHelper::$rookDir[$k];
						if(!(PachCreateHelper::$legalPosition[$r][$nextPosition] & PachCreateHelper::$positionMask[4]))
						{
							// 目标位置不合理
							break;
						}
							
						if(!$this->_board[$nextPosition])	// 目标位置无子
						{
							$flexibleValue[$r] += 4;
						}
						else if($this->_board[$nextPosition] & $sideTag)	// 目标位置有本方棋子
						{
							break;
						}
						else	// 目标位置有对方棋子
						{
							$flexibleValue[$r] += 4;
							break;
						}
					}
				}
			}
			
			// 炮的灵活性
			for($i=9; $i<=10; $i++)
			{
				$position = $this->_pieces[$sideTag + $i];
				if(!$position)
				{
					continue;
				}
				for($k=0; $k<4; $k++)	// 4个方向
				{
					$overFlag = 0;
					for($j=1; $j<10; $j++)	// 横向最多8个位置，纵向最多9个位置
					{
						$nextPosition = $position + $j*PachCreateHelper::$cannonDir[$k];
						if(!(PachCreateHelper::$legalPosition[$r][$nextPosition] & PachCreateHelper::$positionMask[5]))
						{
							// 目标位置不合理
							break;
						}
							
						if(!$this->_board[$nextPosition])	// 目标位置无子
						{
							if(!$overFlag)	// 未翻山
							{
								$flexibleValue[$r] += 3;
							}
						}
						else	// 目标位置有子
						{
							if(!$overFlag)	// 未翻山，则置翻山标志
							{
								$overFlag = 1;
							}
							else	// 已翻山
							{
								if(!($this->_board[$nextPosition] & $sideTag))	// 对方棋子
								{
									$flexibleValue[$r] += 3;
								}
								break;	// 不论吃子不吃子，都退出此方向搜索
							}
						}
					}
				}
			}
			
			// 卒的灵活性
			for($i=11; $i<=15; $i++)
			{
				$position = $this->_pieces[$sideTag + $i];
				if(!$position)
				{
					continue;
				}
				for($k=0; $k<3; $k++)	// 3个方向
				{
					$nextPosition = $position + PachCreateHelper::$pawnDir[$r][$k];
					if(PachCreateHelper::$legalPosition[$r][$nextPosition] & PachCreateHelper::$positionMask[6])
					{
						if(!($this->_board[$nextPosition] & $sideTag))	// 目标位置没有本方棋子
						{
							$flexibleValue[$r] += 2;
						}
					}
				}
			}
		}*/
		$value = $flexibleValue[0] - $flexibleValue[1] + $wValue - $bValue;
		if($this->_side)
		{
			return -$value;
		}
		else
		{
			return $value;
		}
		
	}

	/**
	 * 切换走棋方
	 */
	public function changeSide()
	{
		$this->_side = 1- $this->_side;
	}
	
	/**
	 * 走一步棋
	 * @param array $move 走棋的起始点，结束点
	 */
	public function makeMove($move)
	{
		$sideTag = 32 - 16*$this->_side;	// 对方将帅的值
		$from = $move[0];
		$dest = $move[1];
		$p = $this->_board[$dest];
		
		// 设置走法栈
		$this->_moveStack[] = [$from, $dest, $p];
		//print_r([$from, $dest, $p]);
		
		// 设置棋子数组
		if($p > 0)
		{
			$this->_pieces[$p] = 0;
		}
		$this->_pieces[$this->_board[$from]] = $dest;
		
		// 设置棋盘数组
		$this->_board[$dest] = $this->_board[$from];
		$this->_board[$from] = 0;
		
		$this->_ply++;
		
		$this->changeSide();
		
		return $p==$sideTag;
	}
	
	/**
	 * 撤销走棋
	 */
	public function unMakeMove()
	{
		$move = array_pop($this->_moveStack);
		//print_r($move);
		
		$this->_ply--;
		$this->changeSide();
		
		$from = $move[0];
		$dest = $move[1];
		$p = $move[2];
		
		// 设置棋盘数组
		$this->_board[$from] = $this->_board[$dest];
		$this->_board[$dest] = $p;
		
		// 设置棋子数组
		if($p > 0)
		{
			$this->_pieces[$p] = $dest;
		}
		$this->_pieces[$this->_board[$from]] = $from;
	}
	
	/**
	 * 极大点搜索算法
	 * @param int $depth 搜索深度
	 */
	public function maxSearch($depth)
	{$this->times++;
		$best = -3000;
		$moveArray = [];
		if($depth == 0)
		{
			return $this->evaluate();
		}
		
		$this->genAllMove($moveArray);

		foreach ($moveArray as $move)
		{
			$this->makeMove($move);
			$value = $this->minSearch($depth - 1);
			$this->unMakeMove();
			//echo 'max:$value='.$value.'$best='.$best.'<br/>';
			//print_r($this->_pieces);exit();
			if($value > $best)
			{
				$best = $value;
				//echo 'enter2';print_r($move);echo '$depth='.$depth;
				if($depth == $this->_maxDepth)
				{
					$this->_bestMove = $move;
					//echo 'max';
				}
			}

		}
		
		return $best;		
	}
	
	/**
	 * 极小点搜索算法
	 * @param int $depth 搜索深度
	 */
	public function minSearch($depth)
	{$this->times++;
		$best = 3000;
		$moveArray = [];
		if($depth == 0)
		{
			return $this->evaluate();
		}
		
		$this->genAllMove($moveArray);
//print_r($moveArray);
		foreach ($moveArray as $move)
		{
			$this->makeMove($move);
			$value = $this->maxSearch($depth - 1);
			$this->unMakeMove();
			//echo '$value='.$value;
			//echo 'min:$value='.$value.'$best='.$best.'<br/>';
			if($value < $best)
			{//echo 'enter';print_r($move);echo '$depth='.$depth;
				$best = $value;
				if($depth == $this->_maxDepth)
				{
					$this->_bestMove = $move;
					//echo 'mix';
				}
			}	
		}
		
		return $best;
	}
	
	/**
	 * 极大极小搜索算法
	 * @param int $depth 搜索深度
	 */
	public function minMaxSearch($depth=3)
	{
		if($this->_side == 0)
		{
			$this->maxSearch($depth);
		}
		else
		{
			$this->minSearch($depth);
		}
	}
	
	/**
	 * 合并之后的极大极小搜索算法
	 * @param int $depth 搜索深度
	 */
	public function negaMaxSearch($depth=3)
	{
		$this->times++;
		$best = -30000;
		$moveArray = [];
		if($depth == 0)
		{
			return $this->evaluate();
		}
		
		$this->genAllMove($moveArray);
		
		foreach ($moveArray as $move)
		{
			$this->makeMove($move);
			$value = -$this->negaMaxSearch($depth - 1);
			$this->unMakeMove();
			if($value > $best)
			{
				$best = $value;
				if($depth == $this->_maxDepth)
				{
					$this->_bestMove = $move;
				}
			}
		
		}
		
		return $best;
	}
	
	/**
	 * Alpha-Beta搜索算法
	 */
	public function alphaBetaSearch($depth=3, $alpha, $beta)
	{
		$this->times++;
		$moveArray = [];
		if($depth == 0)
		{
			return $this->evaluate();
		}
		
		$this->genAllMove($moveArray);
		
		foreach ($moveArray as $move)
		{
			$this->makeMove($move);
			$value = -$this->alphaBetaSearch($depth - 1, -$beta, -$alpha);
			$this->unMakeMove();
			if($value >= $beta)
			{
				return $beta;
			}
			if($value > $alpha)
			{
				$alpha = $value;
				if($depth == $this->_maxDepth)
				{
					$this->_bestMove = $move;
				}
			}
		
		}
		
		return $alpha;
	}
	
}